package leetcode;

/***
 * 题目：合并两个有序链表
 * 链接：https://leetcode.cn/problems/merge-two-sorted-lists/description/
 */
public class Merge {
    static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) {
            this.val = val; this.next = next;
        }
    }

    /**
     * 左神基础解法
     * 思路：一个结果链表，两个待轮询链表，一个辅助节点链表（指向结果链表的最后一个节点）
     * 找到最小链表，另一个为次链表，结果链表指向最小链表，每次curr1与curr2的val相比
     * 谁小，head的next节点指向谁，之后curr指向下一个节点，即next，因为上一个已经比较过了
     * 然后将辅助链表指向结果链表的最后一个节点
     * 循环往复，至curr1或者curr2循环完毕。
     * 看谁还有剩下的未遍历的，将pre的next指向剩下的。
     * pre=head，操作了pre，等于操作了head，他们共用的是一个head地址   * @param head1
     * @param head2
     * @return
     */
    public static ListNode mergeTwoLists(ListNode head1, ListNode head2) {
        // 判断是否有空节点
        if (head1 == null || head2 == null) {
            return head1 == null ? head2 : head1;
        }
        //根据大小选择头结点
        ListNode head = head1.val < head2.val ? head1 : head2;
        //定义辅助节点
        ListNode curr1 = head.next;
        ListNode curr2 = head == head1 ? head2 : head;
        //当前组装好的链表的最后一个节点
        ListNode pre = head;
        //比较curr1、curr2的大小
        while (curr1 != null && curr2 != null) {
            if(curr1.val < curr2.val) {
                pre.next = curr1;
                curr1 = curr1.next;
            }else {
                pre.next = curr2;
                curr2 = curr2.next;
            }
            pre = pre.next;
        }
        pre.next = curr1 != null ? curr1 : curr2;
        return head;
    }
    public static ListNode mergeTwoListsByDG(ListNode list1, ListNode list2) {
        if(list1 == null) return list2;
        if(list2 == null) return list1;
        if(list1.val < list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        }else{
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
    public static ListNode mergeTwoLists2(ListNode list1, ListNode list2) {
       // 有空链表直接返回另一个
        if(list1==null || list2==null) {
            return list1==null ? list2 : list1;
        }
        ListNode head = list1.val <= list2.val ? list1 : list2;
        ListNode curr1 = head.next;
        ListNode curr2 = head == list1 ? list2 : list1;
        ListNode pre = head;

        while (curr1 != null && curr2 != null) {
            if(curr1.val <= curr2.val) {
                pre.next = curr1;
                curr1 = curr1.next;
            }else {
                pre.next = curr2;
                curr2 = curr2.next;
            }
            // pre指向最新的链表最后一个
            pre = pre.next;
        }
        pre.next = curr1 != null ? curr1 : curr2;
        return head;
    }

    public static void main(String[] args) {
        ListNode node1 = getNode1();
        ListNode node2 = getNode2();
        ListNode head = mergeTwoLists2(node1, node2);
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
    }
    private static ListNode getNode1() {
        // 创建第一个节点
        ListNode head = new ListNode(1);
        System.out.println(head);
        // 用于遍历和连接节点的指针
        // 此处使用的是引用地址
        ListNode current = head;
        // 创建并连接后续节点
        current.next = new ListNode(3);
        current = current.next;

        current.next = new ListNode(6);
        current = current.next;

        current.next = new ListNode(11);
        current = current.next;

        current.next = new ListNode(12);
        return head;
    }

    private static ListNode getNode2() {
        // 创建第一个节点
        ListNode head = new ListNode(3);
        System.out.println(head);
        // 用于遍历和连接节点的指针
        // 此处使用的是引用地址
        ListNode current = head;
        // 创建并连接后续节点
        current.next = new ListNode(3);
        current = current.next;

        current.next = new ListNode(7);
        current = current.next;

        current.next = new ListNode(10);
        current = current.next;

        current.next = new ListNode(12);
        current = current.next;

        current.next = new ListNode(14);
        return head;
    }
}
